#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
typedef int ElemType;
typedef struct
{
    ElemType *elem;
    int lenth;
}sstable;
void Initss(sstable ST,int len)
{
    ST.lenth=len;
    ST.elem=(ElemType*)malloc(sizeof(ElemType)*ST.lenth);
    srand(time(NULL));
    int i;
    for(i=0;i<ST.lenth;i++)
    {
        ST.elem[i]=rand()%100;
    }
}
void prinss(sstable  ST)
{
    int i;
    for(i=0;i<ST.lenth;i++)
    {
        printf("%3d",ST.elem[i]);
    }
    printf("\n");
}
//交换
void swap(int &a,int &b)
{
    int tmp;
    tmp=a;
    a=b;
    b=tmp;
}
//把某个子树调整为大根堆的函数
void Adjustdown(ElemType A[],int k ,int len)
{
    int dad=k;
    int son=2*dad+1;//左孩子的下标
    while (son<len)
    {
        if (son+1<len&&A[son]<A[son+1])
        {
            son++;
        }
        if (A[son]>A[dad])
        {
            swap(A[son],A[dad]);
            dad=son;
            son=2*dad+1;
        }
        else{
            break;
        }
    }
}
void Heapsort(ElemType A[],int len)
{
    int i;
    for(i=len/2-1;i>=0;i--)
    {
        Adjustdown(A,i,len);
    }
    swap(A[0],A[len-1]);
    for(i=len-1;i>1;i--)
    {
        Adjustdown(A,0,i);//调整剩余元素变为大根堆
        swap(A[0],A[i-1]);//交换根部元素和无序数的数组的最后一个元素
    }
}
int main()
{
    sstable ST;
    Initss(ST,10);
    ElemType A[10]={3,87,2,93,78,56,61,38,12,40};
    ST.lenth=10;
    ST.elem=A;
    prinss(ST);
    Heapsort(A,10);
    prinss(ST);
    return 0;
}
//完全二叉树的高度和n的关系就算log2n，所以Adjustdown函数最高的循环次数就算log2n，所以heapsort函数的
//第一个for循环了n/2次，都二分for循环了n次，总计次数是3/2nlog2n，因此时间复杂度是O(nlog2n)